問３　プログラムの並列実行に関する次の記述を読んで，設問１〜３に答えよ。

　プログラムを並列に実行する方法として，スレッドを使用した並列実行がある。 スレッドを使用した並列実行では，プログラムの中で並列実行が可能な部分を抽出して 複数の処理に分割し，分割した処理を別々のスレッドとして同時に実行する。

　スレッドによる並列実行の例を，図１に示す。プログラム A は，一つのプロセスとして実行され， データ作成，計算処理，結果出力の順に処理が行われる。ここで， 計算処理は n 個の処理に分割して並列実行が可能であり，分割した処理を異なるスレッドで 並列に実行した結果は，スレッドを使わずに計算処理した実行結果と同じであるとする。 計算処理では，スレッドの生成と実行を行い，全てのスレッドの終了を同期処理で待つ。 各スレッドでは，分割した計算処理（部分計算処理）を行う。

図１　スレッドによる並列実行の例

　プログラムＡを実行するコンピュータの構成は，性能が同じである複数の CPU と 各 CPU からアクセス可能な共有メモリで構成されているマルチプロセッサとする。 生成された複数のスレッドは，異なる CPU に割り当てられて同時に実行され， 各スレッドは共有メモリでデータを共有する。マルチプロセッサにおけるスレッドと CPU ，共有メモリの関係を，図２に示す。ここで，データを転送するバスの競合は無いものとする。

図２　マルチプロセッサにおけるスレッド実行

設問１　次の記述中の に入れる正しい答えを， 解答群の中から選べ。

　マルチプロセッサによる並列実行で得られる理想的な高速化率 E は次の式で求められる。

　図１のプログラムＡにおいて，データ作成，計算処理，結果出力の処理時間の割合が 7：90：3 の場合，単一の CPU で実行したときと比べた高速化率を５以上にするには， CPU が最低 個必要である。 ここで，スレッドの生成処理などの並列実行に伴うオーバヘッドは考慮しない。

a に関する解答群

基本情報技術者試験

　プログラムの一部を複数の処理に分割して並列に実行するためには，プログラムの中から 並列実行が可能な部分を抽出する必要がある。並列実行が可能なループの例を， 図３に示す。図３は，i のループに関してループを四つに分割し，分割したそれぞれの ループの処理をスレッドとして並列実行する場合である。ここで，配列のデータは スレッド間で共有され，変数 i はスレッドごとに確保されるものとする。

図３　並列実行が可能なループの例

　プログラムの中から並列実行が可能な部分を抽出する場合，並列に実行しても データの更新と参照の順序が変化しないことを保証する必要がある。 図４に示すプログラム１〜３を，i のループに関して複数のループに分割し， 分割したそれぞれのループの処理を並列に実行する場合の並列実行可能性について考える。 ここで，配列は十分に大きいものとする。

　プログラム１は，ループの中で ，並列実行できない。 プログラム２は，ループの中で ，並列実行できない。 プログラム３は，m の値が不明の場合には並列実行できないが， で あることが保証されていれば並列実行は可能である。

図４　ループのプログラム１〜 ３

b，c に関する解答群

d に関する解答群

基本情報技術者試験

図５　プログラム４の並列実行

解答群